ON A SET OF FUNCTIONS

Chugunova Varvara Valeryevna, Candidate of physico-mathematical sciences, associate professor, sub-department of discrete mathematics, Penza State University,  chugunov@sura.ru

 519.718

The realization of Boolean functions with circuits of unreliable functional elements in bases, contained the function h(x₁,…x_2k+1) from set H_2k+1 is considered. The basis elements are supposed to be prone to inverse faults on element inputs independently from each other with the probability (ε∈(0;1/2)). I this work there are demonstrated: 1) in arbitrary finite full basis B, contained function h(x₁, ..., x_2k+1 ) of set H_2k+1, all Boolean functions are possible to realize with circuits with reliability at most a aε^k+1 + ε^k+2 при ε ≤ 1/48am²2k+1), where a= C^k+1_2k+1 ,m - is the greatest number of element inputs in finite full basis B; 2) in basis B, contained all functions, depended at most on two variables, and the function  h(x₁, ..., x_2k+1) ∈ H_2k+1, functions are possible to realize with asymptotically optimal on reliability circuits, worked with unreliability, asymptotically equal to aε^k+1,  (at ε→0), where a = C^k+1_2k+1 .

boolean functions, asymptotically optimal reliable circuits.